#include<iostream>
#include<algorithm>
#include<string>
#include<unordered_set>
using namespace std;
bool wordBreak(string s, vector<string>& wordDict) {


    int n = wordDict.size();
    vector<bool> dp(s.size() + 1, false);
    dp[0] = true;
    for (int i = 0; i < s.size() + 1; i++) {
        for (int j = 0; j < n; j++) {
            int len = wordDict[j].size();
            if (len <= i) {
                if (s.substr(i - len, len) == wordDict[j] &&
                    dp[i - len] == true) {
                    dp[i] = true;
                }
            }
        }
    }
    return dp[s.size()];



}



